//
// Created by Xu Xiao on 2022/9/30.
//

#ifndef ALGORITHM_22_1_EULERSIEVE_H
#define ALGORITHM_22_1_EULERSIEVE_H

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;


class EulerSieve {
public:
    static pair<int *, bool *> sieve(int n) {
        int *prime = new int[n + 5]{};
        bool *isPrime = new bool[n + 5];
        memset(isPrime, true, n * sizeof(bool));
        for (int i = 2; i <= n; i++) {
            if (isPrime[i])
                prime[++prime[0]] = i;
            for (int j = 1; j <= prime[0] && i * prime[j] <= n; j++) {
                isPrime[i * prime[j]] = false;
                if (i % prime[j] == 0) break;
            }
        }
        return {prime, isPrime};
    }

    static pair<int *, int *> getPrimeTableAndNumsOut(int n) {
        int *numsOut = new int[n + 5];
        auto t = sieve(n);
        auto prime = t.first;
        auto isPrime = t.second;
        for (int j = 2, i = 0; j <= n; j++) {
            if (!isPrime[j]) {
                numsOut[i] = j;
                i++;
            }
        }
        delete[] isPrime;
        return {prime, numsOut};
    }

    static pair<int *, bool *> getPrimeAndIsPrimeTable(int n) {
        return sieve(n);
    }

};


#endif //ALGORITHM_22_1_EULERSIEVE_H
